<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    869. Similar String Groups
   </h1>
   <p>
    Two strings
    <code>
     X
    </code>
    &nbsp;and
    <code>
     Y
    </code>
    &nbsp;are similar if we can swap two letters (in different positions) of
    <code>
     X
    </code>
    , so that&nbsp;it equals
    <code>
     Y
    </code>
    .
   </p>
   <p>
    For example,
    <code>
     "tars"
    </code>
    &nbsp;and
    <code>
     "rats"
    </code>
    &nbsp;are similar (swapping at positions
    <code>
     0
    </code>
    and
    <code>
     2
    </code>
    ), and
    <code>
     "rats"
    </code>
    and
    <code>
     "arts"
    </code>
    are similar, but
    <code>
     "star"
    </code>
    is not similar to
    <code>
     "tars"
    </code>
    ,
    <code>
     "rats"
    </code>
    , or
    <code>
     "arts"
    </code>
    .
   </p>
   <p>
    Together, these form two connected groups by similarity:
    <code>
     {"tars", "rats", "arts"}
    </code>
    and
    <code>
     {"star"}
    </code>
    .&nbsp; Notice that
    <code>
     "tars"
    </code>
    and
    <code>
     "arts"
    </code>
    are in the same group even though they are not similar.&nbsp; Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.
   </p>
   <p>
    We are given a list
    <code>
     A
    </code>
    of strings.&nbsp; Every string in
    <code>
     A
    </code>
    is an anagram of every other string in
    <code>
     A
    </code>
    .&nbsp; How many groups are there?
   </p>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input: </strong>["tars","rats","arts","star"]
<strong>Output: </strong>2</pre>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ol>
    <li>
     <code>
      A.length &lt;= 2000
     </code>
    </li>
    <li>
     <code>
      A[i].length &lt;= 1000
     </code>
    </li>
    <li>
     <code>
      A.length * A[i].length &lt;= 20000
     </code>
    </li>
    <li>
     All words in
     <code>
      A
     </code>
     &nbsp;consist of lowercase letters only.
    </li>
    <li>
     All words in
     <code>
      A
     </code>
     have the same length and are anagrams of each other.
    </li>
    <li>
     The judging time limit has been increased for this question.
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    869. 相似字符串组
   </h1>
   <p>
    如果我们交换字符串&nbsp;
    <code>
     X
    </code>
    中的两个不同位置的字母，使得它和字符串&nbsp;
    <code>
     Y
    </code>
    相等，那么称
    <code>
     X
    </code>
    和
    <code>
     Y
    </code>
    两个字符串相似。
   </p>
   <p>
    例如，
    <code>
     "tars"
    </code>
    和
    <code>
     "rats"
    </code>
    是相似的 (交换
    <code>
     0
    </code>
    与
    <code>
     2
    </code>
    的位置)；&nbsp;
    <code>
     "rats"
    </code>
    和
    <code>
     "arts"
    </code>
    也是相似的，但是
    <code>
     "star"
    </code>
    不与
    <code>
     "tars"
    </code>
    ，
    <code>
     "rats"
    </code>
    ，或
    <code>
     "arts"
    </code>
    相似。
   </p>
   <p>
    总之，它们通过相似性形成了两个关联组：
    <code>
     {"tars", "rats", "arts"}
    </code>
    和
    <code>
     {"star"}
    </code>
    。注意，
    <code>
     "tars"
    </code>
    和
    <code>
     "arts"
    </code>
    是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
   </p>
   <p>
    我们给出了一个不包含重复的字符串列表
    <code>
     A
    </code>
    。列表中的每个字符串都是
    <code>
     A
    </code>
    中其它所有字符串的一个字母异位词。请问
    <code>
     A
    </code>
    中有多少个相似字符串组？
   </p>
   <p>
    <strong>
     示例：
    </strong>
   </p>
   <pre><strong>输入：</strong>["tars","rats","arts","star"]
<strong>输出：</strong>2</pre>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     <code>
      A.length &lt;= 2000
     </code>
    </li>
    <li>
     <code>
      A[i].length &lt;= 1000
     </code>
    </li>
    <li>
     <code>
      A.length * A[i].length &lt;= 20000
     </code>
    </li>
    <li>
     <code>
      A
     </code>
     中的所有单词都只包含小写字母。
    </li>
    <li>
     <code>
      A
     </code>
     中的所有单词都具有相同的长度，且是彼此的字母异位词。
    </li>
    <li>
     此问题的判断限制时间已经延长。
    </li>
   </ol>
   <p>
    <strong>
     备注：
    </strong>
   </p>
   <p>
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 字母异位词[anagram]，一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。
   </p>
  </div>
 </body>
</html>